The stellar mass-luminosity relation is poorly constrained by observations for high mass stars. We describe our program to find eclipsing massive binaries in the Magellanic Clouds using photometry of regions rich in massive stars, and our spectroscopic follow-up to obtain radial velocities and orbits. Our photometric campaign identified 48 early-type periodic variables, of which only 15 (31%) were found as part of the microlensing surveys. Spectroscopy is now complete for 17 of these systems, and in this paper we present analysis of the first two, LMC 172231 and ST2-28, simple detached systems of late-type O dwarfs of relatively modest masses. Our orbit analysis yields very precise masses (2%) and we use tomography to separate the components and determine effective temperatures by model fitting, necessary for determining accurate (0.05-0.07 dex) bolometric luminosities in combination with the light-curve analysis. Our approach allows more precise comparisons with evolutionary theory than previously possible. To our considerable surprise, we find a small, but significant, systematic discrepancy: all of the stars are slightly under-massive, by typically 11% (or over-luminous by 0.2 dex) compared to that predicted by the evolutionary models. We examine our approach for systematic problems, but find no satisfactory explanation. The discrepancy is in the same sense as the long-discussed and elusive discrepancy between the masses measured from stellar atmosphere analysis with the stellar evolutionary models, and might suggest that either increased rotation or convective overshooting is needed in the models. Additional systems will be discussed in future papers of this series, and will hopefully confirm or refute this trend.